\subsection{SQL Query Completion}
\label{sec:completion}

The SQL skeleton produced by the first step, though incomplete,
serves as a good reference in inferring complete and valid SQL queries.
In this step, our technique the remaining incomplete parts: conditions and
aggregates, by rule-based learning and type-directed search, respectively.

\subsubsection{Learning Conditions}
\label{sec:decision_tree}

The problem of learning query \textit{conditions} can be cast as finding
appropriate \textit{rules} that can perfectly divide the whole searching space
into positive part and negative part. In our context, the searching space
contains all tuples generated by joining the input tables, the positive part
are all tuples in the output table, and the negative part are the rest
tuples.

%the rest of tuples. Here our searching space consists of all tuples generated
%by joining input tables. These tuples can be returned by applying our SQL
%skeleton on input database if we remove all holes from the SQL skeleton.

Techniques to efficiently find rules from data has been studied extensively
by many machine learning researchers~\cite{Quinlan:1993, Cohen:1995, Frank:1998}.
Generally, in the machine learning community, there are major two paradigms of
rule learning:

%\begin{itemize}
%\item
\vspace{1mm}
\noindent\textbf{\textit{1. Decision-tree learning~\cite{Quinlan:1993}}}. Given
the positive and negative examples, one can generate a decision
tree, and then extract decision-tree-splitting conditions from the root to
all positive leaf. The extracted conditions can be viewed as the selection
criteria that isolates the output data from the input searching space.


%\item
\vspace{1mm}
\noindent\textbf{\textit{2.``Divide-and-conquer'' strategy~\cite{Pagallo:1990}}}. 
Unlike decision-tree learning, instead of learning a full tree,
this methodology repeatedly determines the most powerful rules for the dataset
that can maximally separate the positive examples from the negative ones, until
no more positive examples are available.

\vspace{1mm}

However, for our problem, both methodologies can not be directly applied.
Learning rules via decision-tree learning is restricted to conjunctive rules,
which is insufficient for many real scenarios. On the
other hand, the generalization ability of the ``divide-and-conquer'' strategy
is quite limited due to overpruning and covering heuristic.

To overcome these two limitations, in our technique, we adapt
the PART learning algorithm~\cite{Frank:1998}, which combines both
rule learning paradigms above. Notably, PART is capable of giving an more
accurate and expressive rule set. Specifically, it utilizes the
``divide-and-conquer'' strategy in that it repeatedly builds rules
and removes the instances it covers until no examples are left.
When creating each rule, it employs a pruned decision tree built from
current set of instance and only makes the leaf with the largest coverage
into the resulting rules, without keeping the whole learned tree in memory.


%In order to use PART, there are two issues that should be considered:

Although PART is a promising algorithm for learning rules from data,
there are two challenges when applying it to our problem:

%We customized PART in the following two aspects to make it applicable
%to our problem:

%\begin{itemize}
%\item
\vspace{1mm}
\noindent {\textbf{\textit{Challenge 1. How to represent tuples.}}}
%the literature of learning from examples~\cite{Mitchell:1997},
In PART, an example data point is represented by a single feature vector.
Therefore, we must transform tuples into appropriate feature representation.
To do so, a straightforward way is simply using concrete values in a tuple
as a feature vector. However, doing so loses much useful structure information
needed in a SQL query.

\vspace{1mm}
%\noindent {\textbf{\textit{Solution 1. Encoding prior knowledge.}}}
We encode existing domain knowledge about SQL query as additional
features, such as, (1) Aggregation, including \CodeIn{COUNT}, \CodeIn{MAX},
\CodeIn{MIN} and \CodeIn{AVG}, whose results might be used in query condition;
and (2) Comparison results between two comparable columns.
The above two additional knowledge encoding permits our technique
to make use of correlations between columns, rather than only values
from each isolated and sequential columns.

%Based on these observations
We add two types of new attributes into feature representation of tuples.

%indicate that not only columns themselves
%are useful for describing a tuple but we also should make use of correlation
%between columns. 

\begin{enumerate}

\item \textit{\textbf{Aggregation Features}}. Aggregation
features are the aggregation results grouped by each \CodeIn{String} type column
over every other columns. Table~\ref{tbl:agg} shows an example.


\item \textit{\textbf{Comparison Features}}. Comparison
feature is the result of comparing two comparable columns. We
consider two possible values:  $\{1, 0\}$,  which represents
means whether two columns under comparison satisfy the predicate or not, respectively.
Table~\ref{tbl:com} shows an example.

%the feature would be $0$. Suppose  the comparison features
%for them are summarized in Table \ref{tbl:com}.

\end{enumerate}

\begin{table}[t]
	\begin{center}
		\begin{tabular}{|c|c|}
		\hline
		\textbf{group by}	& \textbf{aggregation} \\
		\hline
		$C_1$ 				& \textsf{COUNT}($C_2$), \textsf{MAX}($C_3$), \textsf{MIN}($C_3$), \textsf{AVG}($C_3$)\\
		$C_2$ 				& \textsf{COUNT}($C_1$), \textsf{MAX}($C_3$), \textsf{MIN}($C_3$), \textsf{AVG}($C_3$)\\
		\hline
		\end{tabular}
	\end{center}
	\caption{The generated aggregation features for
a table with 3 columns:  $C_1$, $C_2$, and $C_3$, in which
columns $C_1$ and $C_2$ are \textsf{String} type and column $C_3$ is
\textsf{Integer} type.}
	\label{tbl:agg}
\end{table}



\begin{table}[t]
	\begin{center}
		\begin{tabular}{|c|c|}
		\hline
		\textbf{predicate}	& \textbf{comparison result} \\
		\hline
		$C_1=C_2$ 			& 0\\
		$C_1<C_2$ 			& 1\\
		$C_1>C_2$			& 0\\
		\hline
		$C_3=C_4$ 			& 1\\
		$C_3<C_4$ 			& 0\\
		$C_3>C_4$			& 0\\
		\hline
		\end{tabular}
	\end{center}
	\caption{The generated comparison features
for a table with 4 columns: $C_1$, $C_2$, $C_3$,
and $C_4$, in which columns $C_1$ and $C_2$ are \textsf{String} type, and
columns $C_3$ and $C_4$ are \textsf{Integer} type. Columns with
the same type are comparable, such as $C_1$ and $C_2$, and
$C_3$ and $C_4$.
}
	\label{tbl:com}
\end{table}

Combining using concrete tuple values, aggregation
features, and comparison features, our technique is able to
extract expressive feature representation for tuples,
and permits users to encode domain knowledge and structural
information about a SQL query.

%\item
\vspace{1mm}
\noindent {\textit{\textbf{Challenge 2. How to use the learnt rules to complete a SQL query.}}}
PART may return rules including three types of features. For example,
it returns the following rules for our motivating example in Section~\ref{sec:example}:
%. For our
%motivating example there is one rule learned from input tuples. It is

\smallskip
{
\CodeIn{COUNT(enrolled.Course\_key) $>$ 2}
    \CodeIn{\&\& student.level =`senior'}.
}
%\smallskip
\vspace{-2mm}

We need to split the returned rule into two parts: the query selection
condition, and the having condition. To achieve this, we
use $P_o$ to denote predicates related to original features
directly derived by the concrete tuple values,
$P_a$ to denote predicates related to aggregation features and $P_c$ to
denote predicates related to comparison features. For predicate in $P_o$,
we use it to fill condition holes in select clause by comparing selected
column with a constant value. For predicate in $P_a$, we
can use it to fill aggregation holes in having clause.

For our motivating example,
$P_o = \{\CodeIn{student.level =`senior'}\}$, 
$P_a = \{\CodeIn{COUNT(enrolled.Course\_key) $>$ 2}\}$.

After that, our technique adds a having condition such as ``\CodeIn{having COUNT(enrolled.Course\_key)}''
to the SQL query skeleton, and use predicates in $P_c$  to fill the selection condition.
%holes using predicates that compare two columns. There is no such predicate in our motivating example.

%\end{itemize}

\subsubsection{Searching for Aggregates}
\label{sec:agg_search}

The last step in completing a SQL query is searching for aggregates as the projection
columns. Our technique uses a type-directed searching strategy to do this. The whole
searching space includes all possible combinations of table columns and the five supported
aggregates (see Figure~\ref{fig:syntax}). In type-directed search, we leverage the following
information to prune the potential space:

\begin{enumerate}
\item The output values' type in the result column must be compatible with the aggregate's return
type. For instance, if an output column is String type, it must not use aggregates that always
return an Integer type, such as \CodeIn{count} and \CodeIn{sum}.

\item When using arithmetic aggregates such as \CodeIn{max} and \CodeIn{min}, the values
in the output column must have appeared in the input table.
\end{enumerate}

In our experience, the type-directed searching strategy significantly reduces the
searching space and makes our tool find the desirable aggregates faster.
